package ljl.alg.wangzheng_camp.round1.stack_and_queue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 没(mēi)，那么简单
 * */
public class _offer_31_stack_io {
    
    /**
     * 提示：单调栈
     * 做对了可以不用笨办法
     *
     * 令人难受的是，我这个也通过了
     * 你甚至不愿意叫我一声教父
     *
     * */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new LinkedList<>();
        int i = 0, j = 0;
        /*
        * 又在死记硬背哎我透？
        * */
        while (i < pushed.length) {
            // 可以改成不管相等不相等都往里 push
            // 反正下面要判断的
            if (pushed[i] != popped[j]) {
                stack.push(pushed[i++]);
                continue;
            }
            // 相等，一起往后走，没问题吧？
            i++; j++;
            // 相等的完事了看看旧的是不是可以处理了
            while (!stack.isEmpty() && stack.peek() == popped[j]) {
                j++;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
    
    // 我的妈呀太简洁了
    // 这是普通人能想出来的吗
    public boolean validateStackSequences2(int[] pushed, int[] popped) {
        LinkedList<Integer> stack = new LinkedList<>();
        int k = 0;
        for (int i : pushed) {
            stack.push(i);
            while (!stack.isEmpty() && stack.peek() == popped[k]){
                k++;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}
